package model;

import java.util.Stack;
import java.util.Vector;

/**
 *
 * @author Beto
 */
public class Dijkstra {

    public int[] dijkstra(GrafoPonderado G) {
        
        Vertice[] vertices = new Vertice[G.getNumVertices()];
        Vertice atual = null, menor = null, fim = null;
        
        for (int i = 0; i < G.getNumVertices(); i++) {
            vertices[i] = new Vertice(i);
            vertices[i].setDistancia(Integer.MAX_VALUE);
            vertices[i].setAnterior(null);
        }

        Vector<Vertice> trajeto = new Vector<Vertice>();
        trajeto.add(vertices[0]);

        atual = vertices[0];
        atual.setDistancia(0);
        fim = vertices[G.getNumVertices()-1];

        int[] vizinhos = G.vizinhos(atual.getId());
        for (int i = 0; i < vizinhos.length; i++)
            vertices[vizinhos[i]].setAnterior(atual);

        while(!atual.equals(fim)) {
            menor = null;

            for(int i = 0; i < vertices.length; i++) {
                if(!trajeto.contains(vertices[i])) {
                    if(menor == null)
                        menor = vertices[i];

                    if(atual.getDistancia() + pesoEntreVertices(G, atual.getId(), i) < vertices[i].getDistancia()) {
                        if(pesoEntreVertices(G, atual.getId(), i) < Integer.MAX_VALUE) {
                            vertices[i].setDistancia(atual.getDistancia() + pesoEntreVertices(G, atual.getId(), i));
                            vertices[i].setAnterior(atual);
                        }
                    }

                    if(vertices[i].getDistancia() < menor.getDistancia())
                        menor = vertices[i];
                }
            }

            atual = menor;
            trajeto.add(atual);
        }

        Stack<Integer> pilha = new Stack<Integer>();
        atual = trajeto.lastElement();

        do {
            pilha.push(atual.getId());
            atual = atual.getAnterior();
        } while(atual != null);

        int[] menorTrajeto = new int[pilha.size()];
        int count = 0;

        while(!pilha.isEmpty())
            menorTrajeto[count++] = pilha.pop();

        return menorTrajeto;
    }

    private int pesoEntreVertices(GrafoPonderado G, int origem, int destino) {
        if(G.isArco(origem, destino))
            return (int) G.getPeso(origem, destino);
        else
            return Integer.MAX_VALUE;
    }

    private class Vertice {
        private int id;
        private int distancia;
        private Vertice anterior;

        public Vertice(int id) {
            this.id = id;
        }

        public Vertice getAnterior() {
            return anterior;
        }

        public void setAnterior(Vertice anterior) {
            this.anterior = anterior;
        }

        public int getDistancia() {
            return distancia;
        }

        public void setDistancia(int distancia) {
            this.distancia = distancia;
        }

        public int getId() {
            return id;
        }
    }
}


